package com.kevin.Code.Bitwise;

/**
 * @author Vinlee Xiao
 * @Classname CountingBits
 * @Description Leetcode 338. 比特位计数 简单难度 hot 100
 * @Date 2021/11/19 20:19
 * @Version 1.0
 */
public class CountingBits {

    /**
     * 自己思路：
     *
     * @param n
     * @return
     */
    public int[] countBits(int n) {

        int[] result = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            result[i] = countNum(i);
        }

        return result;
    }

    public int countNum(int num) {
        int cnt = 0;


        while (num != 0) {
            num = num & (num - 1);
            cnt++;
        }
        return cnt;
    }


    /**
     * 动态规划
     * 官方题解：
     *
     * @param n
     * @return
     */
    public int[] countBits1(int n) {

        int[] bits = new int[n + 1];
        int highBit = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            bits[i] = bits[i - highBit] + 1;
        }
        return bits;

    }
}
